#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;
typedef struct BSTNode{
    KeyType key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BiTree;

//非递归的创建二叉查找树
int BTSInsert(BiTree &T,KeyType k)
{
    BiTree TreeNew=(BiTree)calloc(1,sizeof(BSTNode)); //新结点申请空间
    TreeNew->key=k; //把值放入
    if(T==NULL)  //树为空，新结点作为树根
    {
        T=TreeNew;
        return 1;
    }
    BiTree p=T,parent;  //p用来查找树
    while (p)
    {
        parent=p;  //存放p结点的父亲
        if(k>p->key)
        {
            p=p->rchild;
        } else if(k<p->key)
        {
            p=p->lchild;
        } else{
            return 0; //相等元素不可以放入查找树，考研一般不会考
        }
    }
    //接下来判断放到父亲的左边还是右边
    if(k>parent->key)  //放到父亲右边
    {
        parent->rchild=TreeNew;
    } else{   //放到父亲左边
        parent->lchild=TreeNew;
    }
    return 1;
}
//递归创建二叉查找树
int BTSInsertRecursion(BiTree &T,KeyType k)
{
    if(T==NULL)
    {
        //为新结点申请空间，第一个根节点作为树根，后面递归再进入的不是树根，是叶子结点
        T= (BiTree)calloc(1,sizeof(BSTNode));
        T->key=k;
        return 1; //代表插入成功
    }
    else if(k<T->key)
        return BTSInsertRecursion(T->lchild,k);
    else if(k>T->key)
        return BTSInsertRecursion(T->rchild,k);
    else
        return 0;
}
void CreateBST(BiTree &T,KeyType* str,int len)
{
    for (int i = 0; i < len; ++i) {
        BTSInsert(T,str[i]); //把某一结点放入二叉查找树
    }
}
//中序遍历
void InOrder(BiTree T)
{
    if(T!=NULL)
    {
        InOrder(T->lchild);
        printf("%3d",T->key);
        InOrder(T->rchild);
    }
}
//查找结点和他的父节点
BiTree BSTSearch(BiTree T,KeyType k,BiTree &parent)
{
    parent=NULL;
    while (T!=NULL&&k!=T->key)
    {
        parent=T;
        if(k<T->key)
        {
            T=T->lchild;
        } else{
            T=T->rchild;
        }
    }
    return T;
}
//删除某个结点
void DeleteNode(BiTree &T,KeyType k)
{
    if(T==NULL)
    {
        return;
    }
    if(T->key>k) //当前结点大于要删除的结点，往左子树找
    {
        DeleteNode(T->lchild,k);
    } else if(T->key<k)  //当前结点小于要删除的结点，往右子树找
    {
        DeleteNode(T->rchild,k);
    } else{  //找到要删除的结点了
        if(T->rchild==NULL)  //右子树为空，左子树直接顶上去
        {
            BiTree tempNode=T;
            T=T->lchild;
            free(tempNode);
        } else if(T->lchild==NULL)  //左子树为空，右子树直接顶上去
        {
            BiTree tempNode=T;
            T=T->rchild;
            free(tempNode);
        } else{  //两边都不为空
            //一般的删除策略是左子树的最大数据或右子树的最小数据
            // 代替要删除的结点（这里采用查找左子树最大数据来代替，最大数据是左子树的最右结点）
            BiTree tempNode=T;
            while (tempNode->rchild!=NULL)
            {
                tempNode=tempNode->rchild;
            }
            T->key=tempNode->key; //把tempNode对应的值替换到要删除的值的位置上
            DeleteNode(T->lchild,tempNode->key); //在左子树中找到tempNode的值，把其删除
        }

    }
}
//二叉排序树新建，中序遍历，查找
int main() {
    BiTree T=NULL;
    KeyType str[7]={45,54,98,24,5,62,43};
    CreateBST(T,str,7);
    InOrder(T); //中序遍历二叉查找树是由小到大的
    printf("\n");
    BiTree search,parent; //查找值的当前结点和父结点
    search=BSTSearch(T,98,parent);
    if(search)
    {
        printf("find key=%d\n",search->key);
        printf("Its parent is=%d\n",parent->key);
    } else{
        printf("not find\n");
    }
    DeleteNode(T,5);
    InOrder(T);
    return 0;
}
